class Disjoint_sets():
    def __init__(self):
        self.p={} #node:parent
        self.rank={} #node:rank
    def makeset(self,x):
        self.p[x]=x
        self.rank[x]=0
    def union(self,x,y):
        self.link(self.find_set(x), self.find_set(y))
    def link(self,x,y): #x and y are roots: p[x]==x and p[y]==y
        if self.rank[x]>self.rank[y]:
            self.p[y]=x
        else:
            self.p[x]=y
            if self.rank[x]==self.rank[y]:
                self.rank[y]+=1
    def find_set(self,x):
        if x!=self.p[x]:
            self.p[x]=self.find_set(self.p[x])
        return self.p[x]
    
